/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package Practica6.practica;

import Practica6.structures.Heap;
import java.util.Comparator;

/**
 *
 * @author miguel
 */
public class MyHeap<Type> extends Heap<Type> {

    @Override
    public void add(Type t) {
        this.inserta(t);
    }

    @Override
    public String toString() {
        String elementos = "";
        for (int i = 0; i < N; i++) {
            elementos += heap[i].toString() + " \n";
        }
        return "MyHeap{" + "heap=" + heap + " N=" + N + ", comparator=" + comparator + ",\n"
                + "elementos: " + elementos + "\n}";
    }

    @Override
    public Type getMin() {
        return this.eliminaMinimo();
    }
    private Type[] heap;
    private int N;
    private Comparator<Type> comparator;

    public MyHeap(int capacidadInicial) {
        heap = (Type[]) new Object[capacidadInicial + 1];
        N = 0;
    }

    public MyHeap() {
        this(1);
    }

    public MyHeap(int initCapacity, Comparator<Type> comparator) {
        this.comparator = comparator;
        heap = (Type[]) new Object[initCapacity + 1];
        N = 0;
    }

    public MyHeap(Comparator<Type> comparator) {
        this(1, comparator);
    }

    public MyHeap(Type[] llaves) {
        N = llaves.length;
        heap = (Type[]) new Object[llaves.length + 1];
        System.arraycopy(llaves, 0, heap, 1, N);
        for (int k = N / 2; k >= 1; k--) {
            sink(k);
        }
        assert esHeapMinimo();
    }

    public boolean esVacio() {
        return N == 0;
    }

    public int tamano() {
        return N;
    }

    public Type min() {
        if (esVacio()) {
            throw new RuntimeException("Underflow en la cola de prioridades");
        }
        return heap[1];
    }

    private void redimensionar(int capacidad) {
        assert capacidad > N;
        Type[] temp = (Type[]) new Object[capacidad];
        for (int i = 1; i <= N; i++) {
            temp[i] = heap[i];
        }
        heap = temp;
    }

    public void inserta(Type x) {
        if (N == heap.length - 1) {
            redimensionar(2 * heap.length);
        }


        heap[++N] = x;
        swim(N);
        assert esHeapMinimo();
    }
    
    public boolean esta(Type t){
        for(Type s: this.heap){
            if(s.equals(t)){
                return true;
            }
        }
        return false;
    }

    public Type eliminaMinimo() {
        if (N == 0) {
            throw new RuntimeException("Underflow en la cola de prioridades");
        }
        intercambia(1, N);
        Type min = heap[N--];
        sink(1);
        heap[N + 1] = null;
        if ((N > 0) && (N == (heap.length - 1) / 4)) {
            redimensionar(heap.length / 2);
        }
        assert esHeapMinimo();
        return min;
    }

    private void swim(int k) {
        while (k > 1 && mayor(k / 2, k)) {
            intercambia(k, k / 2);
            k = k / 2;
        }
    }

    private void sink(int k) {
        while (2 * k <= N) {
            int j = 2 * k;
            if (j < N && mayor(j, j + 1)) {
                j++;
            }
            if (!mayor(k, j)) {
                break;
            }
            intercambia(k, j);
            k = j;
        }
    }

    private boolean mayor(int i, int j) {
        if (comparator == null) {
            return ((Comparable<Type>) heap[i]).compareTo(heap[j]) > 0;
        } else {
            return comparator.compare(heap[i], heap[j]) > 0;
        }
    }

    private void intercambia(int i, int j) {
        Type swap = heap[i];
        heap[i] = heap[j];
        heap[j] = swap;
    }

    private boolean esHeapMinimo() {
        return esHeapMinimo(1);
    }

    private boolean esHeapMinimo(int k) {
        if (k > N) {
            return true;
        }
        int izquierdo = 2 * k, derecho = 2 * k + 1;
        if (izquierdo <= N && mayor(k, izquierdo)) {
            return false;
        }
        if (derecho <= N && mayor(k, derecho)) {
            return false;
        }
        return esHeapMinimo(izquierdo) && esHeapMinimo(derecho);
    }
}
